package jun;

import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * @author ：冯涛滔
 * @date ：Created in 2020-6-8 9:47
 * @description：
 * @modified By：
 * @version:
 */
public class Jun08 {
    /**
     * create by: 冯涛滔
     * description: https://leetcode-cn.com/problems/coin-change/submissions/
     * create time: 2020-6-8 10:14
     * @params [coins, amount]
     * @return int
     */
    public static int coinChange(int[] coins, int amount) {
        if(coins.length == 0){
            return -1;
        }
        //遍历coins升序排列 每次更新 1-amount的最优解 dp[i] = coins[j]/i  + dp[j%i];
        int[] dp =  new int[amount+1];
        Arrays.fill(dp,amount+1);
        dp[0] = 0;
        for(int i = 1; i <= amount;i++){
            for(int j = 0;j < coins.length;j++){
                if(i - coins[j] >= 0){
                    dp[i] = Math.min(dp[i],dp[i-coins[j]] + 1);
                }
            }
        }

        return dp[amount] == (amount+1) ? -1 : dp[amount];
    }
    public boolean canWinNim(int n) {
        boolean[] dp = new boolean[4];
        for(int i = 1; i <= n; i++) {
            boolean ret = true;
            ret &= dp[(i - 1) % 4];
            if(i >= 2) {
                ret &= dp[(i - 2) % 4];
            }
            if(i >= 3) {
                ret &= dp[(i - 3) % 4];
            }
            dp[i % 4] = !ret;
        }
        return dp[n % 4];
    }
    /* 返回游戏最后先手和后手的得分之差 */
    int stoneGame(int[] piles) {
        int n = piles.length;
        // 初始化 dp 数组
        Pair[][] dp = new Pair[n][n];
        for (int i = 0; i < n; i++)
            for (int j = i; j < n; j++)
                dp[i][j] = new Pair(0, 0);
        // 填入 base case
        for (int i = 0; i < n; i++) {
            dp[i][i].fir = piles[i];
            dp[i][i].sec = 0;
        }
        // 斜着遍历数组
        for (int l = 2; l <= n; l++) {
            for (int i = 0; i <= n - l; i++) {
                int j = l + i - 1;
                // 先手选择最左边或最右边的分数
                int left = piles[i] + dp[i+1][j].sec;
                int right = piles[j] + dp[i][j-1].sec;
                // 套用状态转移方程
                if (left > right) {
                    dp[i][j].fir = left;
                    dp[i][j].sec = dp[i+1][j].fir;
                } else {
                    dp[i][j].fir = right;
                    dp[i][j].sec = dp[i][j-1].fir;
                }
            }
        }
        Pair res = dp[0][n-1];
        return res.fir - res.sec;
    }
    class Pair{
        int fir;
        int sec;

        public Pair(int fir, int sec) {
            this.fir = fir;
            this.sec = sec;
        }
    }
    /**
     * create by: 冯涛滔
     * description: https://leetcode-cn.com/problems/longest-increasing-subsequence/
     * dp[i] =以i为终点最长的升序字串长度
     * create time: 2020-6-8 15:22
     * @params [nums]
     * @return int
     */
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        dp[0] = 1;
        Arrays.fill(dp,1);
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if(nums[j]<nums[i]){
                    dp[i] = Math.max(dp[j]+1,dp[i]);
                }
            }
        }
        int max = 0;
        for (int i = 0; i < dp.length; i++) {
            max = Math.max(dp[i],max);
        }
        return max;
    }
    /**
     * create by: 冯涛滔
     * description: https://leetcode-cn.com/problems/longest-common-subsequence/
     * create time: 2020-6-8 15:46
     * dp[i][j] = t1(1-i) 和 t2(1-j) 的公共字符串长度
     * @params [text1, text2]
     * @return int
     */
    public int  longestCommonSubsequence(String text1, String text2) {
        char[] t1 = text1.toCharArray();
        char[] t2 = text2.toCharArray();
        int length1 = t1.length;
        int length2 = t2.length;
        int[][] dp = new int[length1+1][length2+1];
        for (int i = 1; i < length1 +1; i++) {
            for (int j = 1; j < length2 +1; j++) {
                if (t1[i-1] == t2[j-1]){
                    // 这边找到一个 lcs 的元素，继续往前找
                    dp[i][j] = 1+ dp[i-1][j-1];
                }else {
                    //谁能让 lcs 最长，就听谁的
                    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        return dp[length1][length2];
    }
    /**
     * create by: 冯涛滔
     * description: https://leetcode-cn.com/problems/triangle/ 120. 三角形最小路径和
     * create time: 2020-6-8 16:29
     * @params [triangle]
     * @return int
     */
    public static int minimumTotal(List<List<Integer>> triangle) {
        //dp[i][j] i第几层 j下标 值最小路径和
        //这里数组空间浪费了一半 懒得优化了
        int[][] dp = new int[triangle.size()][triangle.get(triangle.size()-1).size()];
        for (int i = 0; i < dp.length; i++) {
            Arrays.fill(dp[i],Integer.MAX_VALUE);
        }
        dp[0][0] = triangle.get(0).get(0);//初始化第一个位置
        for (int i = 1; i < triangle.size(); i++) {//从第二层开始遍历
            List<Integer> list = triangle.get(i);
            for (int j = 0; j < list.size(); j++) {
                dp[i][j] = Math.min(dp[i-1][j],j-1>=0?dp[i-1][j-1]:Integer.MAX_VALUE) + list.get(j);
            }
        }
        int len = dp.length - 1;
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < dp[len].length; i++) {
            min = Math.min(min,dp[len][i]);
        }
        return min;
    }
    /**
     * create by: 冯涛滔
     * description: https://leetcode-cn.com/problems/maximum-product-subarray/ 152. 乘积最大子数组
     * create time: 2020-6-8 17:06
     * @params [nums]
     * @return int
     */
    public int maxProduct(int[] nums) {
        int len = nums.length;
        if (len == 0) {
            return 0;
        }
        int preMax = nums[0];
        int preMin = nums[0];

        // 滚动变量
        int curMax;
        int curMin;

        int res = nums[0];
        for (int i = 1; i < len; i++) {
            if (nums[i] >= 0) {
                curMax = Math.max(preMax * nums[i], nums[i]);
                curMin = Math.min(preMin * nums[i], nums[i]);
            } else {
                curMax = Math.max(preMin * nums[i], nums[i]);
                curMin = Math.min(preMax * nums[i], nums[i]);
            }
            res = Math.max(res, curMax);
            // 赋值滚动变量
            preMax = curMax;
            preMin = curMin;
        }
        return res;
    }
    /**
     * create by: 冯涛滔
     * description: https://leetcode-cn.com/problems/russian-doll-envelopes/ 354. 俄罗斯套娃信封问题
     * create time: 2020-6-8 21:14
     * @params [envelopes]
     * @return int
     */
    public int maxEnvelopes(int[][] envelopes) {

        Arrays.sort(envelopes, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0]==o2[0]?o1[1]-o2[1]:o1[0]-o2[0]; //宽度排高度排
            }
        });
        int[] dp = new int[envelopes.length];
        Arrays.fill(dp,1);
        int res = 1;
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; i-j>=0 ; j++) {
                if(envelopes[i][0]>envelopes[i-j][0]&&envelopes[i][1]>envelopes[i-j][1]){
                    dp[i] = Math.max(dp[i],dp[i-j]+1);
                    res = Math.max(res,dp[i]);
                }
            }
        }
        return res;
    }
    public static void main(String[] args) {

    }
}
